#include <iostream>
#include <stack>
#include <string>
#include <vector>

using std::cout;
using std::endl;
using std::stack;
using std::string;
using std::vector;

class Tool
{
    enum Priority
    {
        PLUS_SUB = 0,
        MULTIPLY_DIVIDE,
        BRACKET
    };

public:
    static Tool *getInstance()
    {
        if (inst_)
        {
            return inst_;
        }
        inst_ = new Tool();
        return inst_;
    }

    Priority getPriority(char ch)
    {
        Priority pri;
        if (ch == '-' || ch == '+')
            pri = Priority::PLUS_SUB;
        else if (ch == '*' || ch == '/')
            pri = Priority::MULTIPLY_DIVIDE;
        else
            pri = Priority::BRACKET;

        return pri;
    }

    bool isPush(char top, char ch)
    {
        if (ch == ')')
            return false;
        if (top == '(')
            return true;
        // 只有当当前符号优先级大于栈顶符号时，才直接进行压栈操作，否则都需要先出栈
        Priority top_p = getPriority(top), ch_p = getPriority(ch);
        return ch_p > top_p;
    }

    void infixToSuffix(const string &expr, vector<char> &suffixVec)
    {
        stack<char> cs;
        for (char ch : expr)
        {
            // 首先判断当前字符是否为数字, 如果是，直接push到后缀容器中
            if (ch >= '0' && ch <= '9')
            {
                suffixVec.push_back(ch);
            }
            else
            {
                // 如果不为空，判断是否需要将当前运算符压栈
                char topCh;
                while (!cs.empty())
                {
                    topCh = cs.top();
                    if (isPush(topCh, ch))
                    {
                        break;
                    }
                    else
                    {
                        cs.pop();
                        if (topCh == '(')
                            break;
                        suffixVec.push_back(topCh);
                    }
                }
                // 为空或者需要push
                if (ch != ')')
                    cs.push(ch);
            }
        }

        while (!cs.empty())
        {
            if (cs.top() != '(')
                suffixVec.push_back(cs.top());
            cs.pop();
        }
    }

private:
    Tool() {}
    Tool(const Tool &tool) {}

private:
    static Tool *inst_;
};

Tool *Tool::inst_ = nullptr;

void test1()
{
    Tool *inst = Tool::getInstance();
    vector<char> result;
    inst->infixToSuffix("1+2*3", result);

    for (char ch : result)
    {
        printf("%c ", ch);
    }
    printf("\n");
    result.clear();

    inst->infixToSuffix("1+2*3/(1+2)", result);

    for (char ch : result)
    {
        printf("%c ", ch);
    }
    printf("\n");

    result.clear();
    inst->infixToSuffix("2+(4+6)/2+6/3", result);

    for (char ch : result)
    {
        printf("%c ", ch);
    }
    printf("\n");
}

int main(int args, char *argv[])
{

    test1();
    return 0;
}